Search Results

Documents authored by Kari, Jarkko

Document
DOI: 10.4230/LIPIcs.MFCS.2020.12
Decidability in Group Shifts and Group Cellular Automata

Authors: Pierre Béaur and Jarkko Kari

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.
Cite as

Pierre Béaur and Jarkko Kari. Decidability in Group Shifts and Group Cellular Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beaur_et_al:LIPIcs.MFCS.2020.12,
  author =	{B\'{e}aur, Pierre and Kari, Jarkko},
  title =	{{Decidability in Group Shifts and Group Cellular Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.12},
  URN =		{urn:nbn:de:0030-drops-127206},
  doi =		{10.4230/LIPIcs.MFCS.2020.12},
  annote =	{Keywords: group cellular automata, group shifts, symbolic dynamics, decidability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.14
Decidability and Periodicity of Low Complexity Tilings

Authors: Jarkko Kari and Etienne Moutot

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this paper we study low-complexity colorings (or tilings) of the two-dimensional grid ℤ². A coloring is said to be of low complexity with respect to a rectangle if there exists m,n∈ℕ such that there are no more than mn different rectangular m× n patterns in it. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. Suppose we are given at most nm rectangular patterns of size n× m. If Nivat’s conjecture is true, one can only build periodic colorings out of these patterns - meaning that if the m× n rectangular patterns of the coloring are among these mn patterns, it must be periodic. The main contribution of this paper proves that there exists at least one periodic coloring build from these patterns. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Finally, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. The results also extend to other convex shapes in place of the rectangle.
Cite as

Jarkko Kari and Etienne Moutot. Decidability and Periodicity of Low Complexity Tilings. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kari_et_al:LIPIcs.STACS.2020.14,
  author =	{Kari, Jarkko and Moutot, Etienne},
  title =	{{Decidability and Periodicity of Low Complexity Tilings}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.14},
  URN =		{urn:nbn:de:0030-drops-118752},
  doi =		{10.4230/LIPIcs.STACS.2020.14},
  annote =	{Keywords: Nivat’s conjecture, domino problem, decidability, low pattern complexity, 2D subshifts, symbolic dynamics}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2016.4
Tutorial on Cellular Automata and Tilings (Tutorial)

Authors: Jarkko Kari

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Cellular automata (CA) are massively parallel systems where a regular grid of finite symbols is updated according to a synchronous application of the same local update rule everywhere. A closely related concept is that of Wang tiles where a local relation between neighboring symbols determines allowed combinations of symbols in the grid. In this tutorial we start with classical results on cellular automata, such as the Garden-of-Eden theorems, the Curtis-Hedlund-Lyndon-theorem and the balance property of surjective cellular automata. We then discuss Wang tiles and, in particular, the concept of aperiodicity and the undecidability of the domino problem. The domino problem is the decision problem to determine if a given Wang tile set admits any valid tilings of the grid. We relate Wang tiles to cellular automata, and establish a number of undecidability results for cellular automata.
Cite as

Jarkko Kari. Tutorial on Cellular Automata and Tilings (Tutorial). In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kari:LIPIcs.STACS.2016.4,
  author =	{Kari, Jarkko},
  title =	{{Tutorial on Cellular Automata and Tilings}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.4},
  URN =		{urn:nbn:de:0030-drops-57054},
  doi =		{10.4230/LIPIcs.STACS.2016.4},
  annote =	{Keywords: cellular automata, wang tiles, decision problems, dynamics}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.RTA.2013.1
Pattern Generation by Cellular Automata (Invited Talk)

Authors: Jarkko Kari

Published in: LIPIcs, Volume 21, 24th International Conference on Rewriting Techniques and Applications (RTA 2013)

Abstract
A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply by constants 3 and 3/2 in base 6. We discuss the connections of these automata to some difficult open questions in number theory, and we pose several further questions concerning pattern generation in cellular automata.
Cite as

Jarkko Kari. Pattern Generation by Cellular Automata (Invited Talk). In 24th International Conference on Rewriting Techniques and Applications (RTA 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 21, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kari:LIPIcs.RTA.2013.1,
  author =	{Kari, Jarkko},
  title =	{{Pattern Generation by Cellular Automata}},
  booktitle =	{24th International Conference on Rewriting Techniques and Applications (RTA 2013)},
  pages =	{1--3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-53-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{21},
  editor =	{van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2013.1},
  URN =		{urn:nbn:de:0030-drops-40490},
  doi =		{10.4230/LIPIcs.RTA.2013.1},
  annote =	{Keywords: cellular automata, pattern generation, Z-numbers}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact